package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by 朱城委 on 2021/7/8.<br><br>
 *
 * 杨辉三角
 */
public class Topic118 {
    public static void main(String[] args) {
        Topic118 instance = new Topic118();

        System.out.println(instance.generate(1));
        System.out.println(instance.generate(2));
        System.out.println(instance.generate(3));
        System.out.println(instance.generate(4));
        System.out.println(instance.generate(5));
    }

    public List<List<Integer>> generate(int numRows) {
        if(numRows < 1) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        generate(numRows, result);

        return result;
    }

    public void generate(int numRows, List<List<Integer>> result) {
        List<Integer> temp = new ArrayList<>();
        temp.add(1);

        if(numRows == 1) {
            result.add(temp);
            return ;
        }

        generate(numRows - 1, result);
        List<Integer> lastResult = result.get(numRows - 2);
        for(int i = 1; i < numRows - 1; i++) {
            temp.add(lastResult.get(i - 1) + lastResult.get(i));
        }

        temp.add(1);
        result.add(temp);
    }

    public List<List<Integer>> generate2(int numRows) {
        if(numRows < 1) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        result.add(Arrays.asList(1));
        for(int i = 1; i < numRows; i++) {
            List<Integer> subResult = result.get(i - 1);
            List<Integer> temp = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if(j < 1 || j >= subResult.size()) {
                    temp.add(1);
                }
                else {
                    temp.add(subResult.get(j - 1) + subResult.get(j));
                }
            }

            result.add(temp);
        }

        return result;
    }
}
